/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

 const int MAX = 100000;  // 预设最大路径数（根据树规模预估，防止溢出）

 typedef struct TreeNode TreeNode;
 
 /**
  * @brief 将整数路径转换为“->”连接的字符串形式
  * @param path 当前路径节点值的数组
  * @param pathTop 当前路径长度
  * @return 拼接好的字符串路径（需调用者释放）
  */
 char *processData(int *path, int pathTop) {
     // step 1# 初始化字符串缓冲区
     char num[20];  // 临时存放整数转字符串
     char *temp = (char *)malloc(sizeof(char) * 1024);  // 分配路径字符串内存
     temp[0] = 0;  // 初始化为空串
 
     // step 2# 遍历路径数组，构建“1->2->5”格式字符串
     for (int i = 0; i < pathTop; i++) {
         sprintf(num, "%d", path[i]);  // 将整数转换为字符串
         strcat(temp, num);            // 拼接数字
         if (i != pathTop - 1) strcat(temp, "->");  // 非最后一个则添加"->"
     }
     return temp;  // 返回拼接好的字符串路径
 }
 
 /**
  * @brief 深度优先搜索所有从根到叶子的路径
  * @param curNode 当前节点指针
  * @param returnSize 当前已找到的路径数（输出参数）
  * @param pathTop 当前路径深度（用于 path 索引）
  * @param result 存储路径字符串的数组
  * @param path 临时路径数组，保存当前递归路径节点值
  */
 void searchPath(TreeNode *curNode, int *returnSize, int pathTop, char **result, int *path) {
     // step 1# 空节点直接返回
     if (curNode == NULL) return;
 
     // step 2# 将当前节点值加入路径
     path[pathTop++] = curNode->val;
 
     // step 3# 若当前为叶子节点，则将路径转换为字符串并加入结果数组
     if (curNode->left == NULL && curNode->right == NULL) {
         result[(*returnSize)++] = processData(path, pathTop);
     }
 
     // step 4# 递归遍历左右子树
     searchPath(curNode->left, returnSize, pathTop, result, path);
     searchPath(curNode->right, returnSize, pathTop, result, path);
 }
 
 /**
  * @brief 主函数：生成所有从根节点到叶子节点的路径
  * @param root 二叉树根节点
  * @param returnSize 返回路径总数（通过指针传出）
  * @return 所有路径字符串的数组（每个元素为一条路径）
  */
 char** binaryTreePaths(struct TreeNode* root, int* returnSize) {
     // step 1# 初始化路径数组和结果数组
     *returnSize = 0;
     int *path = (int *)malloc(sizeof(int) * MAX);            // 存放临时路径
     char **result = (char **)malloc(sizeof(char *) * MAX);   // 存放结果路径字符串
 
     // step 2# 开始递归搜索路径
     searchPath(root, returnSize, 0, result, path);
 
     return result;  // step 3# 返回路径字符串数组
 }
 